package com.liunian.algorithmstudy.dynamic.subsequence;

public class FindLength718 {

	/**
	 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

	 示例 1：
	 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
	 输出：3
	 解释：长度最长的公共子数组是 [3,2,1] 。

	 示例 2：
	 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
	 输出：5
	 */
	public int findLength(int[] nums1, int[] nums2) {
		int[][] dp = new int[nums1.length + 1][nums2.length + 1];
		int res = 0;
		for (int i = 1; i < nums1.length + 1; i++) {
			for (int j = 1; j < nums2.length + 1; j++) {
				if (nums1[i - 1] == nums2[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
					res = Math.max(res, dp[i][j]);
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		FindLength718 find = new FindLength718();
		System.out.println(find.findLength(new int[]{1, 2, 3, 2, 1}, new int[]{3,2,1,4,7}));
	}

}
